1. Field of the Invention
The present invention relates to a technology for managing memory resources, and in particular, it relates to a technology for managing memory resources used by the execution of an application program and executing a garbage collection process for collecting free memory areas of the memory resources.
2. Description of the Related Art
As a method for efficiently managing limited memory resources without increasing a programmer""s load in a processing system, there is a method called xe2x80x9cgarbage collectionxe2x80x9d (hereinafter called xe2x80x9cGCxe2x80x9d). The GC process specifies free data in a memory and collects a memory area used by the data to use the area for another piece of data.
In the description of GC, a memory resource to be managed is called a xe2x80x9cheapxe2x80x9d. The heap is composed of units of data strings called cells (or objects). Each cell can include pointers pointing to another cell and other data, but excluding pointers.
Outside the heap there is an aggregate of the pointers, such as a register, a stack, etc., to which an application program executed on the processing system can directly refer, and this aggregate is called a root. In the heap, there are both a cell that can be directly or indirectly accessed by a pointer reference from this root and a cell that cannot be accessed in such a way. The former cell can be accessed by the execution of an application program and is called a xe2x80x9clive cellxe2x80x9d, xe2x80x9csurviving cellxe2x80x9d, etc. The latter cell cannot be accessed by the execution of an application program and is called a xe2x80x9cdead cellxe2x80x9d, etc.
The GC judges whether each cell is live or dead in a heap, regards dead cells as xe2x80x9cgarbagexe2x80x9d and collects the xe2x80x9cgarbagexe2x80x9d as an area that can be used by another piece of data.
The GC can be classified into several categories based on the principle of an adopted algorithm. A variety of GC methods are described in detail in xe2x80x9cFeature: The Basics of Garbage Collection and its Recent Trendxe2x80x9d, Information Processing, Vol.35, No.11, Information Processing Society of Japan (1994). Here, a parallel type GC, which is one of the methods, is described.
Processes in which GC is performed in the processing system are largely classified into two categories: a process executed by an application program and a process executed by GC. The former is called a mutator and the latter is called a collector.
According to the basic algorithm of GC, in order to prevent the change in the life/death status of a cell by a mutator, the mutator is temporarily stopped while a collector is executed by the processing system, and the collectors are collectively executed. However, basically the collector must extract all cells that can be reached by sequentially tracing pointers from a root as live cells. In this case, the process load becomes fairly large depending on the amount of live cells. Therefore, the interruption time of a process on the mutator side cannot be neglected.
In order to reduce the execution interruption time of a mutator due to GC, a variety of GC algorithms have been proposed.
Conventionally, a classic GC called collective type GC was used in which the execution of processes by mutators is stopped and a collector collectively collects memories. Since this method stopped a mutator for a long time, the response performance of an application program was degraded, which is a problem.
Then, a method that prevents the interruption for a long time of a mutator by distributing processes by collectors among processes by mutators in terms of time instead of collectively executing GCs and by executing both the processes in parallel one part at a time, was proposed. This is called parallel type GC.
Here, The summaries of both an on-the-fly GC proposed by Mr. Dijikstra et al and a snapshot GC proposed by Mr. Yuasa of the parallel type GCs are described. For detailed information about these GCs, see E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens, xe2x80x9cOn-the-Fly Garbage Collection: An Exercise in Cooperationxe2x80x9d, Communications of the ACM, Vol.21, No.11, pp.966-975 (1978); T. Yuasa, xe2x80x9cReal-Time Garbage Collection on General-Purpose Machinexe2x80x9d, Journal of Systems and Software, Vol.11, pp.181-198 (1990); and T. Yuasa, xe2x80x9cFeature: The Basics of Garbage Collection and its Recent Trend, 3. Real-Time Garbage Collectionxe2x80x9d, Information Processing, Vol.35, No.11, pp.1066-1013, Information Processing Society of Japan (1994).
The on-the-fly GC is obtained by improving a mark and sweep method, which is one of the collective type GC basic algorithms. According to the mark and sweep method, one cycle of GC is divided into two phases, a mark phase and a sweep phase, and is executed.
In the mark phase, first, a root is secured (this process is often specifically called a xe2x80x9croot-insertion phasexe2x80x9d). Then, a process for marking all reached cells while sequentially tracing pointers from the root, is executed.
Then, as a sweep phase, the entire heap is scanned and unmarked cells are collected. Simultaneously, the marks of marked cells are erased in preparation for a subsequent GC. After that, a mark phase (including a root-insertion phase) and a sweep phase are alternately repeated. This is a mark and sweep type GC.
According to the on-the-fly GC, a collector executes a mark and sweep type GC in parallel with a mutator process. In this case, the replacement of pointers by a mutator often occurs in the midst of a mark phase of GC by a collector. In this case, although a dead cell is made a live cell by the replacement of pointers, the live cell is often not marked in a mark phase. Then, this live cell is collected as xe2x80x9cgarbagexe2x80x9d in a subsequent sweep phase, which is another problem. Therefore, according to the on-the-fly GC, each cell in the heap is marked with one of three colors: black, dark black and white. The cell-marking procedure by the on-the-fly GC is described with reference to FIG. 1.
Before the collector starts on-the-fly GC, all cells in a heap are marked white. The collector, first, refers to a root and turns a cell mark directly pointed to by a pointer of this root dark black. (A) in FIG. 1 shows that the marks of cells A and B directly pointed to by the pointer of the root are turned dark black. In FIG. 1 and FIG. 2 referred to later, dark black marks attached to cells are indicated with diagonal lines.
A dark black cell mark indicates that a cell must be marked black again later. Actually, a cell is not marked dark black, but the collector pushes a pointer pointing to the cell to a stack provided for GC (GC stack) (this process is called a xe2x80x9croot insertion processxe2x80x9d, etc.).
Then, the collector turns the dark black cell mark black. In other words, the pointer is popped from the GC stack and the mark of the cell pointed to by the pointer is turned black.
Furthermore, if the black-marked cell stores another pointer pointing to another cell, the collector turns the marks of all cells pointed to by all pointers stored in the cell dark black. In this way, all pointers pointing to other cells stored in the black-marked cell are pushed to the GC stack.(B) in FIG. 1 shows that the dark black mark of cell A shown in (A) is turned black and further the white marks of cells C and D pointed to by the pointers stored in cell A are turned dark black.
According to the on-the-fly GC, a collector process performs the marking described above and in addition, a mutator process performs another marking. If either the root or one of cells in the heap stores a pointer and if a cell pointed to by a stored pointer is marked white, a mutator turn the white mark of the cell pointed to by the pointer dark black. (C) in FIG. 1 shows that as a result of a mutator process, the pointer of the root that points to cell B in (A) is modified to point to cell D and the pointer stored in cell A that points to cell D is modified to point to cell B. (C) in FIG. 1 shows that as a result of these modifications, of the marks of cells B and D that are pointed to by the pointer of the root and the new pointer stored in cell A, respectively, the white mark of cell D is turned dark black.
Then, the collector process performs the marking described above. (D) in FIG. 1 shows that the dark black mark of cell A shown in (A) is turned black and that of cells pointed to by the pointers stored in cell A, the white mark of cell C is turned dark black. If this collector marking continues to proceed, there will be no dark black-marked cell in the future (the GC stack will be empty), and the mark of each cell in the heap will become either white or black. In this way, the mark phase of the on-the-fly GC terminates.
In a succeeding sweep phase, white-marked cells are judged as xe2x80x9cgarbagexe2x80x9d and are collected. Simultaneously, black-marked cells are turned white in preparation for a subsequent GC cycle. After that, a mark phase and a sweep phase are alternately repeated. This is the on-the-fly GC.
In this way, according to GC, even if pointer replacement is generated by the mutator process, dark black marks are turned black in the future by turning the marks of cells pointed to by replaced pointers dark black. Therefore, the problem that the live cells are collected by mistake can be solved.
Next, snapshot GC is described. The snapshot GC is also obtained by improving the mark and sweep method described earlier as in the on-the-fly GC.
According to the snapshot GC, cells that are being used at the time of the start of one specific GC cycle cannot be collected in the sweep phase of the cycle even if the cells might become xe2x80x9cgarbagexe2x80x9d later. Cells the use of which starts by the mutator in one GC cycle cannot be collected in the sweep phase of the cycle even if the cells might become xe2x80x9cgarbagexe2x80x9d later. In other words, according to the snapshot GC, only cells that are already xe2x80x9cgarbagexe2x80x9d at the time of the start of one GC cycle are collected. This is as if the snapshot of the state of use of the heap at the time of the start of one GC cycle was taken and only xe2x80x9cgarbagexe2x80x9d cells included in the snapshot were collected. Cells that become xe2x80x9cgarbagexe2x80x9d in the midst of one GC cycle are collected in the sweep phase after the mark phase of a subsequent cycle.
In the mark phase of the on-the-fly GC, if pointer replacement is generated in either the root or a cell in the heap by the mutator process, the white marks of cells pointed to by replaced pointers are turned dark black. In other words, the replaced pointers are pushed onto the GC stack. However, in the mark phase of the snapshot GC, if a pointer is stored in one cell of the heap by the mutator process and if the mark of a cell pointed to by the pointer stored in the cell before the cell storing the pointer stores the pointer is white, the white mark is turned dark black. That is, if a new pointer is stored in a cell, a pointer stored in the cell before the pointer is stored is pushed onto the GC stack. However, the collector process of the snapshot GC is the same as the collector process of the on-the-fly GC.
The cell marking procedure of the snapshot GC is described with reference to FIG. 2.
(A) in FIG. 2 shows that the marks of cells A and B directly pointed to by the pointer of a root are turned dark black as in the collector process of the on-the-fly GC shown at (A) in FIG. 1.
For example, if the pointer of the root and a pointer stored in cell A are modified to point to cell D and cell B, respectively, by the mutator process, the white mark of cell D that the pointer stored in cell A has pointed to before the modification is turned dark black, as is shown at (B) in FIG. 2.
Furthermore, according to the snapshot GC, the white marks of cells the use of which is started by the mutator process are turned black. The marks of both cells that were live at the time of the start of one GC cycle and cells that were newly used in the midst of the mark phase of the cycle will be turned black in the future by these mark replacement operations. In the subsequent sweep phase, white-marked cells are judged as xe2x80x9cgarbagexe2x80x9d and are collected.
The advantage of the snapshot GC over the on-the-fly GC is that no process for GC is required at the time of the assignment of a pointer pointing to a cell to the root that is performed by the mutator process. In the normal mutator process, pointers pointing to cells are often assigned to the root. Therefore, by removing a GC process load from this assignment, the improvement of the execution performance of an application program can be expected.
In this way, according to the snapshot GC, cells that become xe2x80x9cgarbagexe2x80x9d in the midst of one GC cycle are collected in the sweep phase after the mark phase of a subsequent cycle instead of the sweep phase of the cycle. However, a time period required by the sweep phase of the snapshot GC is the same as a time period required by the sweep phase of the mark and sweep method described earlier. Therefore, although the snapshot GC is of a parallel type, it is considered that the collection efficiency of xe2x80x9cgarbagexe2x80x9d cells has been degraded, since cells that become xe2x80x9cgarbagexe2x80x9d in the midst of one GC cycle are not collected in the sweep phase of the cycle compared with the mark and sweep method. In this way, in a parallel type GC, the improvement of the collection efficiency of xe2x80x9cgarbagexe2x80x9d cells is a big problem.
It is an object of the present invention to improve the process efficiency of parallel type GC.
In one aspect of the present invention, it is judged that higher process efficiency of the entire GC can be obtained if the subsequent collection of free cells in a partial marking GC, which is a kind of parallel type GC, should be executed in either a full GC cycle or a partial GC cycle, based on the state of the collection of free cells that is performed in a full GC cycle or partial GC cycle in the past, and a subsequent GC cycle to be executed is selected based on this judgment result.
In another aspect of the present invention, if a cell judged to be free in a mark phase is processed in the first place, the cell is not collected only based on the judgment result, but is processed again in a mark phase and the free cell is collected from a heap based on the result. In this way, even a cell, the period of use of which is short, such as a cell, the use of which is started by the execution of an application program and is terminated immediately after, can be securely collected.
In another aspect of the present invention, if the first pointer that is stored in a cell being used in a heap and that points to another cell in the heap, is modified to the second pointer by the execution of an application program, the pointer pointing to the cell in which the first pointer is stored is reported. A memory management unit newly judges whether a cell that is pointed to by the second pointer stored in a cell pointed to by the reported pointer is being used in the heap by the execution of an application program. In this way, even a cell, the period of use of which is short, such as a cell, the use of which starts at the time of the execution of an application program and is terminated immediately after, can be securely checked and the cell can be securely collected, if the cell is judged to be free.
In another aspect of the present invention, if the first pointer that is stored in a cell being used in a heap and that points to another cell in the heap, is modified to the second pointer by the execution of an application program and if a cell pointed to by the first pointer has never been processed in a mark phase after the judgment of the state of use of cells recently performed in a full GC cycle, the first pointer is reported. The memory management unit newly judges whether a cell pointed to by the first pointer that is stored in a cell pointed to by the reported pointer is being used in the heap by the execution of an application program. In this way, the number of pointers to be reported to the memory management unit can be reduced, and a process load can be reduced accordingly.
In another aspect of the present invention, if the first pointer that is stored in a cell being used in a heap and that points to another cell in the heap, is modified to the second pointer by the execution of an application program and if only a cell pointed to by the first pointer has never been processed in a mark phase after the judgment of the state of use of cells recently performed in a full GC cycle, the second pointer is reported. A memory management unit newly judges whether a cell that is pointed to by the second pointer stored in a cell pointed to by the reported pointer is being used in the heap by the execution of an application program. In this way, the number of pointers to be reported to the memory management unit can be reduced, and a process load can be reduced accordingly.
In this way, by any aspect of the present invention, the process efficiency of a parallel type GC can be improved.